Reste dans une division par p premier - Corrigé

Énoncé

Dans chaque cas, déterminer le reste dans la division euclidienne de \(n\) par \(p\) .

1.  \(n=3^9\)  par  \(p=7\)

2.  \(n=4^{23}\)  par  \(p=11\)

3.  \(n=6^{21}\)  par  \(p=11\)

4.  \(n=8^{48}\)  par  \(p=23\)   

Solution

1. D'après le petit théorème de Fermat (forme faible), on a : \(3^7 \equiv 3 \ [7]\) . 
On en déduit que :  \(\begin{align*}3^9 \equiv 3^7 \times 3^2 \equiv 3 \times 3^2 \equiv 3 \times 9 \equiv 3 \times 2 \equiv 6 \ [7]\end{align*}\)
donc le reste dans la division euclidienne de \(n=3^9\) par \(p=7\) est \(r=6\) .

2. D'après le petit théorème de Fermat (forme faible), on a :  \(4^{11} \equiv 4 \ [11]\) . 
On en déduit que :  \(\begin{align*}4^{23} \equiv (4^{11})^2 \times 4 \equiv 4^2 \times 4 \equiv 16 \times 4 \equiv 5 \times 4 \equiv 20 \equiv 9 \ [11]\end{align*}\)  
donc le reste dans la division euclidienne de \(n=4^{23}\) par \(p=11\) est \(r=9\) .

3. D'après le petit théorème de Fermat (forme faible), on a : \(6^{11} \equiv 6 \ [11]\) .
D'après le petit théorème de Fermat (forme forte), comme \(11\) ne divise pas \(6\) , on a : \(6^{10} \equiv 1 \ [11]\) .
On en déduit que :  \(\begin{align*}6^{21} \equiv 6^{11} \times 6^{10} \equiv 6 \times 1 \equiv 6 \ [11]\end{align*}\)  
donc le reste dans la division euclidienne de \(n=6^{21}\) par \(p=11\) est \(r=6\) .

4. D'après le petit théorème de Fermat (forme faible), on a : \(8^{23} \equiv 8 \ [23]\) . 
On en déduit que :  \(\begin{align*}8^{48} \equiv (8^{23})^2 \times 8^{2} \equiv 8^2 \times 8^2 \equiv (64)^2 \equiv (-5)^2 \equiv 25 \equiv 2 \ [23]\end{align*}\)  
donc le reste dans la division euclidienne de \(n=8^{48}\) par \(p=23\) est \(r=2\) .